package com.game.path
{

	import flash.geom.Point;

	public class PathFinder
	{
		
		public static function find(iniPoint:Point,finPoint:Point,level:Array,ignore:Boolean=false):Array {
			var openList:Array = [];
			var closeList:Array = [];
			//afegim el primer node a la openlist
			var newTile:TileUnit = new TileUnit(iniPoint,0,0,0);
			newTile.parentTile = null;
			openList.push(newTile);
			//executem per primera vegada la funcio bucle
			var camino:Array = searching(finPoint,openList,closeList,level,ignore);
			return camino;
		}
		public static function searching(finPoint:Point,openList:Array,closeList:Array,level:Array,ignore:Boolean):Array {
			if (openList.length == 0) {
				return null;
			}
			var tileMenorF:TileUnit = openList[0];
			var switchIndex:int = 0;
			for (var a:int = 0; a < openList.length; a++) {
				if (openList[a].F < tileMenorF.F) {
					tileMenorF = openList[a];
					switchIndex = a;
				}
				//finalitzaem quan                      
				if (openList[a].pos.x == finPoint.x) {
					if (openList[a].pos.y == finPoint.y) {
						//trobem el tile final
						var camino:Array = [];
						var tileAct:TileUnit = openList[a];
						camino.push(tileAct);
						while (tileAct.parentTile != null) {
							camino.push(tileAct.parentTile);//TODO hanish: unshift
							tileAct = tileAct.parentTile;
						}
						return camino;
					}
				}
			}
			closeList.push(tileMenorF);
			openList.splice(switchIndex,1);
			var possibleMovement:Array = [{i:0,j:1},{i:-1,j:0},{i:1,j:0},{i:0,j:-1}];
			for (var c:int=0; c<possibleMovement.length; c++) {
				var xTile:int = tileMenorF.pos.x + possibleMovement[c].j;
				var yTile:int = tileMenorF.pos.y + possibleMovement[c].i;
				//Check if we visited already this cell
				var existCloseList:Boolean = false;
				for (var m:int = 0; m < closeList.length; m++) {
					if (closeList[m].pos.x == xTile && closeList[m].pos.y == yTile) {
						existCloseList = true;
					}
				}
				//Are we inside the map on an empty cell?
				if (level[yTile]!=null &&level[yTile][xTile]!=null && (level[yTile][xTile] == 0 ||   (level[yTile][xTile] == 3 && ignore==true)  ) && existCloseList == false) {
					//creamos el tile temporal para poder ver si existe en la lista abierta
					// G = 10 for tile horiz or vert & 14 for diagonal
					var G:int = 0;
					
					//H = 10*(abs(currentX-targetX) + abs(currentY-targetY)) ;
					
					var H:Number =10*(((xTile - finPoint.x) < 0 ? -(xTile - finPoint.x) : (xTile - finPoint.x))+((yTile - finPoint.y) < 0 ? -(yTile - finPoint.y) : (yTile - finPoint.y)));
						//10 * ((xTile - finPoint.x) ^ ((xTile - finPoint.x) >> 31)) - ((xTile - finPoint.x) >> 31) + ((yTile - finPoint.y) ^ ((yTile - finPoint.y) >> 31)) - ((yTile - finPoint.y) >> 31);
					//F = G+H
					var F:Number = G + H;
					var newTile:TileUnit = new TileUnit(new Point(xTile,yTile),G,H,F);
					newTile.parentTile = tileMenorF;
					//comprovem si el tile temporal (newTile) esta a la openList
					var exist:Boolean = false;
					var indexTemp:int = 0;
					for (var n:int = 0; n < openList.length; n++) {
						if (openList[n].pos.x == newTile.pos.x && openList[n].pos.y == newTile.pos.y) {
							exist = true;
							indexTemp = n;
						}
					}
					//no esta a la openList (l'afegim)
					if (exist == false) {
						openList.push(newTile);
						//trace("pushing");
					}
					//si esta a la openList...        
					if (exist == true) {
						//compare his G
						if (openList[indexTemp].H < tileMenorF.H) {//TODO hanish: was G
							//recalculem
							//H = 10*(abs(currentX-targetX) + abs(currentY-targetY)) 
							openList[indexTemp].H =  10*(((xTile - finPoint.x) < 0 ? -(xTile - finPoint.x) : (xTile - finPoint.x))+((yTile - finPoint.y) < 0 ? -(yTile - finPoint.y) : (yTile - finPoint.y)));
							//F = G+H
							openList[indexTemp].F = openList[indexTemp].G + openList[indexTemp].H;
							openList[indexTemp].parentTile = tileMenorF;
						}
					}
				}
			}
			return searching(finPoint,openList,closeList,level,ignore);
		}
	}
}